package algorithmicFoundation.homework.day2;


import edu.princeton.cs.algs4.WeightedQuickUnionUF;

/**
 * 渗流
 * 用于建模渗流模型
 *
 * @author 86155
 * @date 2025/07/30
 */
public class Percolation {

    /**
     * 网格
     * 1:open
     * 0:close
     */
    private int[][] grid;

    /**
     * 存储节点联通关系
     */
    private WeightedQuickUnionUF union;

    /**
     * 节点个数
     */
    private int sites;

    /**
     * 打开的节点个数
     */
    private int openSites = 0;

    public Percolation(int n) {
        // 左上角坐标为（1，1）
        if (n <= 0) {
            // 不合法
            throw new IllegalArgumentException("n must bigger than 0");
        }
        //初始化网格
        this.grid = new int[n][n];
        this.sites = n * n;
        //初始化两个虚拟节点
        this.union = new WeightedQuickUnionUF(sites + 2);
    }

    private void verify(int row, int col) {
        if (row >= 1 && row <= this.grid.length && col >= 1 && col <= this.grid.length) {
            return;
        }
        throw new IllegalArgumentException("argument must be positive: " + row + "," + col);
    }

    /**
     * opens the site (row, col) if it is not open already
     *
     * @param row 行
     * @param col 列
     */
    public void open(int row, int col) {
        verify(row, col);
        if (isOpen(row, col)) {
            return;
        }
        //把当前节点打开
        //计数
        this.openSites++;
        this.grid[row - 1][col - 1] = 1;
        //把当前节点 变为一维坐标 公式 (row - 1)*n + col - 1
        int currSite = (row - 1) * grid.length + col - 1;
        //连接上下左右已经打开的节点
        if (row > 1 && isOpen(row - 1, col)) {
            //上
            int upSite = (row - 2) * grid.length + col - 1;
            this.union.union(currSite, upSite);
        }
        if (row < grid.length && isOpen(row + 1, col)) {
            //下
            int downSite = row * grid.length + col - 1;
            this.union.union(currSite, downSite);
        }
        if (col > 1 && isOpen(row, col - 1)) {
            //左
            int leftSite = (row - 1) * grid.length + col - 2;
            this.union.union(currSite, leftSite);
        }
        if (col < grid.length && isOpen(row, col + 1)) {
            //右
            int rightSite = (row - 1) * grid.length + col;
            this.union.union(currSite, rightSite);
        }
        //采取动态链接虚拟节点
        // 动态连接虚拟节点
        if (row == 1) {
            // 顶部行节点 -> 顶部虚拟节点
            union.union(currSite, sites);
        }
        if (row == grid.length) {
            // 底部行节点 -> 底部虚拟节点
            union.union(currSite, sites + 1);
        }

    }

    /**
     * is the site (row, col) open?
     *
     * @param row 行
     * @param col 列
     * @return boolean
     */
    public boolean isOpen(int row, int col) {
        verify(row,col);
        return grid[row - 1][col - 1] == 1;
    }

    /**
     * is the site (row, col) full?
     *
     * @param row 行
     * @param col 列
     * @return boolean
     */
    public boolean isFull(int row, int col) {
        verify(row,col);
        //当前节点有无水覆盖
        //把当前节点 变为一维坐标 公式 (row - 1)*n + col - 1
        int site = (row - 1) * grid.length + col - 1;
        return union.find(this.sites) == union.find(site) && grid[row - 1][col - 1] == 1;
    }

    /**
     * 开放站点数量
     * returns the number of open sites
     *
     * @return int
     */
    public int numberOfOpenSites() {
        return openSites;
    }

    /**
     * does the system percolate?
     *
     * @return boolean
     */
    public boolean percolates() {
        // 虚拟两个空节点，上下各一个如果这俩节点为一个root 说明渗流
        //上面的节点就在index 为sites
        //下面的节点坐标sites + 1
        return union.find(sites) == union.find(sites + 1);
    }


    public static void main(String[] args) {
        Percolation percolation = new Percolation(3);
        System.out.println(percolation.numberOfOpenSites());
//        percolation.open(1, 1);
//        percolation.open(1, 2);
//        percolation.open(1, 3);
//        percolation.open(2, 3);
//        percolation.open(3, 3);
        System.out.println(percolation.percolates());
        System.out.println(percolation.isFull(1, 1));
        System.out.println(percolation.isOpen(1, 3));
    }
}
